﻿#pragma once

template<class T,class K>
struct AVLTreeNode
{
	//使用键值对_val来存储节点内的数据值
	pair<T, K> _val;
	//left表示指向该节点左孩子节点的指针
	AVLTreeNode<T, K>* _left;
	//right表示指向该节点右孩子节点的指针
	AVLTreeNode<T, K>* _right;
	//parent表示指向该节点父节点的指针
	AVLTreeNode<T, K>* _parent;
	//_bf内存储节点的平衡因子
	int _bf;

	
	AVLTreeNode(const pair<T, K>& x)
		:_val(x)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{
		
	}

};


template<class T,class K>
class AVLTree
{
	//将表示节点的变量重命名，简化书写
	typedef AVLTreeNode<T, K> Node;
public:
	

	bool Insert(const pair<T, K>& x)
	{
		//当更节点为空时就直接将root指向新创建的节点
		if (root == nullptr)
		{
			root = new Node(x);
			return true;
		}
		//创建变量cur从根节点进行查找值为x的节点
		Node* cur = root;
		//parent用于表示cur节点的父节点指针
		Node* parent = nullptr;
		//一直查找到cur指向空
		while (cur)
		{
			//当前节点内地数据值小于x，就说明新节点应该在该节点的右边
			if (cur->_val.first < x.first)
			{
				parent = cur;
				cur = cur->_right;

			}
			//当前节点内地数据值大于x，就说明新节点应该在该节点的左边
			else if (cur->_val.first > x.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			//查找到值相同的节点就直接返回false
			else
			{
				return false;
			}
		}
		//创建值为x的节点
		cur = new Node(x);

		//判断新创建的节点是parent节点左孩子还是右孩子
		//若节点内的数据值比parent指向的节点内的数据小就为左孩子
		if (parent->_val.first > x.first)
		{
			parent->_left = cur;
		}
		//若节点内的数据值比parent指向的节点内的数据大就为右孩子
		else
		{
			parent->_right = cur;

		}
		//将新创建的节点内的_parent指向其父节点
		cur->_parent = parent;
		//更新平衡因子
		while (parent)
		{
			if (parent->_left == cur)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == -1 || parent->_bf == 1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == -2 || parent->_bf == 2)
			{
				if (parent->_bf == -2 && cur->_bf == -1)
				{
					//右单旋
					RotateR(parent);

				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					//左单旋
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					//左右双旋
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					//右左双旋
					RotateRL(parent);
				}
				break;
			 
			}
			else
			{
				assert(false);
			}

		}
		return true;

	}


	Node* Find(const T&x)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* cur=root;
		while (cur)
		{
			if (cur->_val.first < x)
			{
				cur = cur->_right;
			}
			else if (cur->_val.first > x)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;

	}


	void InOrder()
	{
		_InOrder(root);
		cout << endl;
	}



	bool IsBalanceTree()
	{
		return _IsBalanceTree(root);
	}


	int  Height()
	{
		return _Height(root);
	}


	int Size()
	{
		return _Size(root);
	}


private:
	//root表示AVL树内的根结点指针
	Node* root = nullptr;

	//右单旋
	void RotateR(Node* Parent)
	{
		//保存要进行右单旋的左孩子节点指针到SubL
		Node* SubL = Parent->_left;
		//保存SubL的右孩子节点指针到SubLR
		Node* SubLR = SubL->_right;
		
		//当h高度不为0时才将SubL的父指针指向Parent
		if (SubLR != nullptr)
		{
			SubLR->_parent = Parent;
		}
		//保存Parent的父节点指针到ppNode
		Node* ppNode = Parent->_parent;
		//将Parent的左孩子指针指向SubLR，父节点指针指向SubL
		Parent->_left = SubLR;
		Parent->_parent = SubL;
		//将SubL的右孩子节点指针指向Parent
		SubL->_right = Parent;

		//判断ppNode是否是根节点以下判断也可以写作Parent!=root
		if (ppNode != nullptr)
		{
			if (ppNode->_left == Parent)
			{
				ppNode->_left = SubL;
			}
			else
			{
				ppNode->_right = SubL;
			}
			SubL->_parent = ppNode;
			
		}
		else
		{
			root = SubL;
			SubL->_parent = nullptr;
		}
		
		//更新Parent和SubL的平衡因子
		Parent->_bf = 0;
		SubL->_bf = 0;

		
	}

	//左单旋
	void RotateL(Node* Parent)
	{
		//保存要进行左单旋的右孩子节点指针SubR
		Node* SubR = Parent->_right;
		//保存SubR的左孩子节点指针SubRL
		Node* SubRL = SubR->_left;
		
		//当h高度不为0时才将SubR的父指针指向Parent
		if (SubRL != nullptr)
		{
			SubRL->_parent = Parent;
		}
		//保存Parent的父节点指针到ppNode
		Node* ppNode = Parent->_parent;
		//将Parent的右孩子指针指向SubRL，父节点指针指向SubR
		Parent->_right = SubRL;
		Parent->_parent = SubR;
		//将SubR的右孩子节点指针指向Parent
		SubR->_left = Parent;

		//判断ppNode是否是根节点以下判断也可以写作Parent!=root
		if (ppNode != nullptr)
		{
			if (ppNode->_left == Parent)
			{
				ppNode->_left = SubR;
			}
			else
			{
				ppNode->_right = SubR;
			}
			SubR->_parent = ppNode;
		}
		else
		{
			root = SubR;
			SubR->_parent = nullptr;
		}
		//更新平衡因子
		SubR->_bf = 0;
		Parent->_bf = 0;
	}


	//左右双旋
	void RotateLR(Node* Parent)
	{
		//保存要进行左右单旋的左孩子节点指针SubL
		Node* SubL = Parent->_left;
		//保存SubL的右孩子节点指针SubLR
		Node* SubLR = SubL->_right;
		//使用bf保存SubLR的平衡因子
		int bf = SubLR->_bf;
		//以节点SubL节点进行左旋
		RotateL(SubL);
		//以节点Parent节点进行右旋
		RotateR(Parent);
		//更新平衡因子
		//当h等于0时
		if (bf == 0) 
		{
			SubL->_bf = 0;
			SubLR->_bf = 0;
			Parent->_bf = 0;
		}
		//当新插入的节点为SubLR的右孩子节点时
		else if(bf==1)
		{
			SubL->_bf = -1;
			Parent->_bf = 0;
			SubLR->_bf = 0;
		}
		//当新插入的节点为SubLR的左孩子节点时
		else if (bf == -1)
		{
			SubL->_bf = 0;
			SubLR->_bf = 0;
			Parent->_bf = 1;
		}
		//当出现其他的情况时就说明出现了错误，直接断言错误
		else
		{
			assert(false);
		}

	}


	//右左单旋
	void RotateRL(Node* Parent)
	{
		//保存要进行右左单旋的右孩子节点指针SubR
		Node* SubR = Parent->_right;
		//保存SubR的左孩子节点指针SubRL
		Node* SubRL = SubR->_left;
		//使用bf保存SubRL的平衡因子
		int bf = SubRL->_bf;

		//以节点SubR节点进行右旋
		RotateR(SubR);
		//以节点Parent节点进行左旋
		RotateL(Parent);

		//更新平衡因子
		if (bf == 0)
		{
			SubR->_bf = 0;
			SubRL->_bf = 0;
			Parent->_bf = 0;
		}
		//当新插入的节点为SubRL的右孩子节点时
		else if (bf == 1)
		{
			SubR->_bf = 0;
			SubRL->_bf = 0;
			Parent->_bf = -1;

		}
		//当新插入的节点为SubRL的左孩子节点时
		else if (bf == -1)
		{
			SubRL->_bf = 0;
			Parent->_bf = 0;
			SubR->_bf = 1;
		}
		//当出现其他的情况时就说明出现了错误，直接断言错误
		else
		{
			assert(false);
		}

	}



	void _InOrder(Node* cur)
	{
		if (cur == nullptr)
		{
			return;
		}
		_InOrder(cur->_left);
		cout << cur->_val.first <<":" << cur->_val.second << endl;
		_InOrder(cur->_right);

	}

	int _Height(Node* cur)
	{
		if (cur == nullptr)
		{
			return 0;
		}
		int Left = _Height(cur->_left);
		int Right = _Height(cur->_right);
		return Left > Right ? Left + 1 : Right + 1;
	}


	bool _IsBalanceTree(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}

		int HLeft = _Height(root->_left);
		int HRight = _Height(root->_right);
		int diff = HRight-HLeft;

		if (abs(diff) >= 2)
		{
			cout << root->_val.first << "⾼度差异常" << endl;
			return false;
		}
		if (root->_bf != diff)
		{
			cout << root->_val.first << "平衡因子异常" << endl;
			return false;
		}
		// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);


	}


	int _Size(Node* cur)
	{
		if (cur == nullptr)
		{
			return 0;
		}

		return 1 + _Size(cur->_left) + _Size(cur->_right);

	}




};



void TestAVLTree1()
{
	AVLTree<int, int> t;
	// 常规的测试⽤例
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// 特殊的带有双旋场景的测试⽤例
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert({ e, e });
		//cout << "Insert:" << e<<"->";
		//cout << t.IsBalanceTree() << endl;

	}
	t.InOrder();
	cout << t.IsBalanceTree() << endl;
}


void TestAVLTree2()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << t.IsBalanceTree() << endl;
	cout << "Insert:" << end2 - begin2 << endl;
	
	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;
	size_t begin1 = clock();
	// 确定在的值
	/*for (auto e : v)
	{
	t.Find(e);
	}*/
	// 随机值
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
}


